package com.sicheng.lc.周赛.分类.图论;

import java.util.Arrays;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/31 10:54
 */
public class 找到离给定两个节点最近的节点 {
    //https://leetcode.cn/problems/find-closest-node-to-given-two-nodes/
    static final int ITF = 0xafafaf;

    public int closestMeetingNode(int[] edges, int a, int b) {
        // 要求 a和b到同一个点的的较大值最小化
        // 分别从 a,b 出发 统计到某个点 m 的距离
        // 跑一遍就可以得到 到同一个点较大值的最小值的那个点
        int n = edges.length;
        // len1[i],len2[i] 表示从a,b出发到i的距离  一般处理图论问题到不了都是取无穷大表示
        int[] len1 = new int[n];
        int[] len2 = new int[n];
        Arrays.fill(len1, ITF);
        Arrays.fill(len2, ITF);
        int d = 1;
        len1[a] = 0;
        // 从a出发
        for (int i = edges[a]; i >= 0 && len1[i] == ITF; i = edges[i]) {
            len1[i] = d;
            d++;
        }
        int res = -1;
        int best = ITF;
        if (len1[b] != ITF) {
            res = b;
            best = len1[b];
        }
        d = 1;
        len2[b] = 0;
        int i = edges[b];

        // 从b出发 一边走一边统计结果
        for (; i >= 0 && len2[i] == ITF; i = edges[i]) {
            len2[i] = d;
            // a,b都能到达i
            if (len1[i] != ITF && len2[i] != ITF) {
                int t = Math.max(len1[i], len2[i]);
                if (t < best) {
                    best = t;
                    res = i;
                } else if (t == best) {
                    res = Math.min(res, i);
                }
            }
            d++;
        }
        return res;
    }


    public static void main(String[] args) {
        找到离给定两个节点最近的节点 s = new 找到离给定两个节点最近的节点();
        int[] e = {1, 2, -1};
        System.out.println(s.closestMeetingNode(e, 0, 2));
    }
}
